本场链接:Educational Codeforces Round 71

闲话

这场对于我1400想上1600(单场的话)要做出A_{E貌似,我这场只有A}C的结果,看对比是+50分,然后要加200分大概出D也是不够的,如果手速快好像可以加多点就是了.然后C题真的好怪啊,,,数字位置对准花了我好长时间.读题和写代码调试的速度还是需要提高.

A. There Are Two Types Of Burgers

题目大意:一个汉堡要$2$片面包和$1$片牛肉.一份鸡腿堡要$2$片面包和$1$片鸡肉.一共有$b$份面包,$p$份牛肉,$f$份鸡肉.一个汉堡卖$h$元,一份鸡腿堡卖$c$元.问最多能赚多少钱.

数据范围:
$1 \leq b,p,f \leq 100$
$1 \leq h,c \leq 100$

思路

由于数据范围极小,所以可以暴力枚举.枚举两种食物的数量,判断是否合法再计算收益即可.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int b,p,f;scanf("%d%d%d",&b,&p,&f);
		int h,c;scanf("%d%d",&h,&c);
		int res = 0;
		for(int x = 0;x <= 100;++x)
		{
			for(int y = 0;y <= 100;++y)
			{
				if(2 * (x + y) <= b && p >= x && f >= y)
				{
					res = max(res,x * h + y * c);
				}
			}
		}
		printf("%d\n",res);
    }
    return 0;
}

B. Square Filling

题目大意:一开始给你两个矩阵$A$和$B$,元素只有$0$或$1$两种.$B$初始是全$0$的.你可以往$B$里染色,一旦你给$(x,y)$这个位置染成了$1$,那么其右边,下边,右下的三个格子也必须跟着染成$1$.你可以在一个已经染色了的格子上染色.问你是否能把$B$矩阵操作成与$A$相同,如果可以,额外输出具体操作方案,注意操作方案并不要求操作次数最小.

数据范围:
$2 \leq n,m \leq 50$

思路

由于数据范围极小,可以暴力遍历$A$中的所有元素,并针对左上角进行染色,最后判断构造出来的新矩阵是否是和$A$一样的即可.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 55;
int a[N][N],b[N][N];
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= m;++j)
			scanf("%d",&a[i][j]);
	vector<pii> op;
    for(int i = 1;i <= n - 1;++i)
    {
    	for(int j = 1;j <= m - 1;++j)
    	{
    		if(a[i][j] == 1)
    		{
    			if(a[i + 1][j] == a[i][j + 1] && a[i + 1][j + 1] == a[i][j + 1] && a[i][j + 1] == 1)
    			{
    				b[i][j] = 1;b[i][j + 1] = 1;
    				b[i + 1][j] = 1;b[i + 1][j + 1] = 1;
    				op.push_back({i,j});
    			}
    		}
    	}
    }
    for(int i = 1;i <= n;++i)
    	for(int j = 1;j <= m;++j)
    		if(a[i][j] != b[i][j])
    			return puts("-1"),0;
    printf("%d\n",op.size());
    for(auto& v : op)	printf("%d %d\n",v.first,v.second);
    return 0;
}

C. Gas Pipeline

题目大意:这鬼题没法翻译,自行看原题面吧.

数据范围:
$2 \leq n \leq 2*10^5$
$1 \leq a,b \leq 10^8$

思路

显然是$dp$求解最小的花费.这个题的坐标对准很是蛋疼,注意这里的第一维指的不是路线上的格子,而是路线上的交接点.
状态;$f[i][j]$表示走到第$i$个交界点时,高度为$j$的所有建造方案中花费最小的.
表示出这个状态之后,考虑有哪些特殊情况要判断是无解的:首先一个要拱起来高度达到2的点,他后面的一位在字符串里的表示应该是$1$.而一个$1$的结束的下一位是不能直接把高度往下拉到$1$的,他必须还要往后一位高度才能是$1$.对于这两种特殊情况,$f[i][1] = INF$
入口:$f[0][1] = b,f[1][1] = a + 2 * b,f[1][2] = 2 * a + 3 * b$
如果$s[2] = '1'$的话,说明第一位必须要建成高度为$2$的,此时$f[1][1] = INF$表示无解.
转移:
①当$s[i] == '1'$或$s[i + 1] == '1'$时$f[i][1] = INF$
$f[i][2] = min(f[i - 1][1] + 2 * (a + b),f[i - 1][2] + 2 * b + a)$即如果本位是高度$2$的他可以是上一位高度为$2$的情况下延续过来,或者是前一位为$1$架高一层.
③$s[i] != '1'$且$s[i + 1] == '0'$时本位可以做高度为$1$的桥.此时$f[i][1] = min(f[i - 1][2] + b + 2 * a,f[i - 1][1] + a + b)$具体原因同上.
出口:$f[n][1]$因为题目要求最后一位必须是高度为$1$的.

不过本题还有一个边角情况就是最后一位的时候下一位是没有字符的,可以给最后一位加一个$0$或者特判处理掉.要不然最后一位高度为$1$的情况不会被计算出来.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
const ll INF = (1ll << 60);
char s[N];
ll f[N][3];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n,a,b;scanf("%d%d%d",&n,&a,&b);
    	scanf("%s",s + 1);s[n + 1] = '0';
    	memset(f,0,sizeof f);
    	f[0][1] = b;f[1][1] = a + 2 * b;f[1][2] = 2 * a + 3 * b;
    	if(s[2] == '1')	f[1][1] = INF;
    	for(int i = 2;i <= n;++i)
    	{
    		if(s[i] == '1' || s[i + 1] == '1')	f[i][1] = INF;
    		f[i][2] = min(f[i - 1][1] + 2 * (a + b),f[i - 1][2] + 2 * b + a);
    		if(s[i] != '1' && s[i + 1] == '0')	f[i][1] = min(f[i - 1][2] + b + 2 * a,f[i - 1][1] + a + b);
    	}
    	// for(int i = 1;i <= n;++i)	cout << i << " " << f[i][1] << " " << f[i][2] << endl;
    	printf("%lld\n",f[n][1]);
    }
    return 0;
}

D. Number Of Permutations

题目大意:给定$n$个二元组.定义整个二元组序列不是牛逼的条件是:第一关键字是不降序列或者第二关键字是不降序列,只要满足一种就是不牛逼的.同样的,如果两者都不满足那这个二元组序列就是牛逼的.问在重排整个二元组的时候,有多少种重排方案使得这个二元组序列是牛逼的.结果对998244353取模.

思路

这题套路非常显然,就是从整体里抠掉部分有序的序列.不过这里是一个二维形式的,因此要做一个简单的冗斥,我一开始完全没意识到冗斥的事就硬做了半天.首先整个序列的排列数是非常好算的,就是$n!$,其次整个序列里要挖掉第一关键字有序的排列和第二关键字有序的排列,最后两者可能有重叠,还需要额外补上第一第二关键字同时有序的序列.
先来看第一关键字有序的序列的数量怎么求:假设整个序列里第一关键字都是不同的,没有一个重复元素,那么排列方式显然就只有一种.如果有,相同的元素之间的位置就是可以任意交换的,比如有两个的时候方案就会增加$2$个,显然内部排列数就是其排列数,即阶乘.而整个序列里可能有多个重复的段,每一段都是独立的,因此适用于乘法原理.因此第一关键字有序的序列数量的球法就比较明显了,就是找出所有第一关键字的出现次数,出现次数依次做阶乘,最后所有的阶乘乘起来就是答案.而第二关键字的数量与之同理.
同时有序的时候,要注意一个特殊情况,即整个序列可能不存在任何一个同时有序的序列,关于这一点可以谈心的先特殊处理出来:先对第一关键字排序再对第二关键字排序,之后考虑整个序列,如果出现了一个元素的第二关键字比后一个元素的第二关键字大的话,就说明在满足第一关键字有序的前提下,第二关键字不可能也有序.因此这种情况的答案就是$0$.反之,与上一种情况比较类似,就是把单个元素换成整个二元组,算出数量然后跟之前一样地算阶乘算乘积就可以了.
关于阶乘只要用递推的形式随便写写取模就完了.
这个题最后还有一个坑点,就是最后一步求答案的时候,表达式里面是存在有负数的,这个时候要应用负数取模,如果不用的话会爆掉数值.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 3e5+7,MOD = 998244353;
#define x first
#define y second
pii a[N];
ll fact[N];
void init()
{
	fact[0] = 1;
	for(int i = 1;i < N;++i)	fact[i] = (fact[i - 1] % MOD * i % MOD) % MOD;
}
int main()
{
	init();
	int n;scanf("%d",&n);
	for(int i = 0;i < n;++i)	scanf("%d%d",&a[i].x,&a[i].y);
	sort(a , a + n);
	int secsorted = 1;
	for(int i = 0;i < n - 1;++i)
		if(a[i].y > a[i + 1].y)
		{
			secsorted = 0;
			break;
		}
	//first sorted
	ll firstres = 1;
	map<int,int> cnt;
	for(int i = 0;i < n;++i)
		++cnt[a[i].x];
	for(auto& __t : cnt)
		firstres = (firstres % MOD * fact[__t.y] % MOD) % MOD;
	//second sorted
	ll secondres = 1;
	cnt = map<int,int>();
	for(int i = 0;i < n;++i)
		++cnt[a[i].y];
	for(auto& __t : cnt)
		secondres = (secondres % MOD * fact[__t.y] % MOD) % MOD;
	//both
	ll bothres = 1;
	map<pii,int> bothcnt;
	if(secsorted)
		for(int i = 0;i < n;++i)
			++bothcnt[a[i]];
	else bothres = 0;
	for(auto& __t : bothcnt)
		bothres = (bothres % MOD * fact[__t.y] % MOD) % MOD;
	printf("%lld",((fact[n] - firstres - secondres + bothres) % MOD + MOD) % MOD);
    return 0;
}

E. XOR Guessing

题目大意:毒瘤在心里想了一个数$x$,这个数$x \in [0,2^{14}-1]$,现在他要你来猜这个数.你最多可以进行两次交互,每次交互输入$100$个数,毒瘤会任意选择一个数,得到$x$和这个数的异或结果返回给你.输出毒瘤心里想的数.

思路

这是一道比较有意思的交互,只不过交互次数很少只有两次,考虑直接构造:定义这样几个变量:$A,B,C,D$分别表示第一次和第二次被毒瘤选上的数,以及两者相应的异或的结果.通过两个式子很容易得到一个结论那就是$A \oplus B = C \oplus D$.因此这个交互题的关键就在于构造两种序列,使得这两个序列里任意的两个元素的异或值各不相同,在各不相同的前提下才可能说找出答案是谁.
具体的构造方案是:$A_i=i$,而$B_i = A_i << 7$,这样的话$A_i与$B_j$两个数异或起来就是相互独立的,并且$A_i \oplus B_i = A_i + B_i$,这也很好理解,异或本来就是不进位加法,这样构造的数本身就不会产生进位也就是相等了. 这样构造之后,得到的结果分别取出来,就有一个式子:$A+B=C\oplus D$.那要怎么构造答案呢?因为$B$是来自$b$序列的,所以他最后$7$为都是$0$.进而我只要把两者的和,也就是$C\oplus D$的前七位抠出来,再把后七位全部搞成$0$.我就得到了$B$.接着,由于$B \oplus x = D$,所以$x = B \oplus D$.最后直接输出就可以了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105],b[105];
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	for(int i = 1;i <= 100;++i)
	{
		a[i] = i;
		b[i] = (i << 7);
	}
	cout << "? ";
	for(int i = 1;i <= 100;++i)	cout << a[i] << " ";
	cout << endl;fflush(stdout);
	int c;cin >> c;fflush(stdout);
	cout << "? ";
	for(int i = 1;i <= 100;++i)	cout << b[i] << " ";
	cout << endl;fflush(stdout);
	int d;cin >> d;fflush(stdout);
	int B = (((c ^ d) >> 7) << 7);
	cout << "! " << (B ^ d);
    return 0;
}

F. Remainder Problem

原题大意:有一个长度为$500000$的序列,初始全为$0$.要求你支持如下两种操作:
①定点修改某一个位置上的值
②查询所有满足下标模某个数为某个数的位置上的数的和.

思路

首先暴力肯定不行,但是暴力的优化很容易想到分块.这题也是一个很明显的分块优化的idea题.具体来说,导致效率不高的点在于如果模数比较小,那么执行的操作会比较多.反之如果模数很大,那么需要统计的信息就会有效地减小.
回到这个题上来,这个题可以分开求解两种情况:当模数$y$比较小的时候,用统计好的信息直接输出,在比较大的时候暴力统计.而统计信息的这一步是①操作完成的,具体来说,设置一个二维数组,第一维表示的是模数是谁,第二维表示的是具体的$x\%$这个模数的结果.当第二个操作需要使用的时候,直接输出$sum[x][y]$即可.
注意还有一个优化点,记录所有的已经增加过到的最大的$x$.在第二步操作的时候,最多只到这个$x$.因为更大的全是$0$没有意义.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int quasize = 707,N = 1000001;
int sum[1005][1005],a[N];
int maxn = 0;
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
		
		if(opt == 1)
		{
			a[x] += y;maxn = max(maxn,x);
			for(int j = 1;j <= quasize;++j)
				sum[j][x % j] += y;	
		}
		else
		{
			if(x <= quasize)	printf("%d\n",sum[x][y]);
			else
			{
				int res = 0;
				for(int i = y;i <= maxn;i += x)
					res += a[i];
				printf("%d\n",res);
			}
		}
    }
    return 0;
}